#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import defaultdict


class Queen:
    def __init__(self, n=8):
        self.n = n
        self.total_cols = set(range(1, n+1))
        self.occupied_cols = [-1] * n

    def run(self):
        self.try_cnt = 0
        self.try_cnt_map = defaultdict(int)
        ret = self.recursive_try()

        return ret

    def recursive_try(self, row_idx=0):
        if row_idx == self.n:
            print(self.occupied_cols)
            return 1

        self.try_cnt += 1
        self.try_cnt_map[self.occupied_cols[0]] += 1 # 第一行选某列分别尝试了多少次
        solutions_cnt = 0

        ava_cols = self.diff(self.occupied_cols)
        for col in ava_cols:
            if not self.is_valid(row_idx, col):
                continue

            self.set_row(row_idx, col)
            solutions_cnt += self.recursive_try(row_idx+1)
            self.clear_row(row_idx)

        return solutions_cnt

    def set_row(self, row_idx, col):
        self.occupied_cols[row_idx] = col

    def clear_row(self, row_idx):
        self.occupied_cols[row_idx] = -1

    def is_valid(self, the_row, the_col):
        def is_45(r1, c1, r2, c2):
            slope = (r1 - r2) / (c1 - c2)       # 计算斜率
            return slope == 1 or slope == -1    # 不可互在对角线

        for row in range(the_row):
            col = self.occupied_cols[row]
            # print((the_row, the_col), (row, col))
            assert the_col != col
            if is_45(the_row, the_col, row, col):
                return False

        return True


    def diff(self, occupied_cols):
        return self.total_cols.difference(occupied_cols)

def test():
    s = Queen()
    solucionts_cnt = s.run()
    print("solutions count", solucionts_cnt)
    print(s.try_cnt_map)

def main():
    test()

if __name__ == "__main__":
    main()
